package com.cqs.leetcode.string;

import java.util.HashMap;
import java.util.Map;

/**
 * lixw
 * 2022/10/23
 **/
public class ScrambleString87 {


    private Map<String, Boolean> cache = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
        cache.clear();
        byte[] bytes = s1.getBytes();
        byte[] bytes2 = s2.getBytes();
        return dfs(bytes, bytes2, 0, bytes.length - 1, 0, bytes2.length - 1);
    }

    private boolean dfs(byte[] bytes1, byte[] bytes2, int left1, int right1, int left2, int right2) {
        if (!check(bytes1, bytes2, left1, right1, left2, right2)) return false;
        String key = left1 + "-" + right1 + "-" + left2 + "-" + right2;
        //System.out.println(key);
        if (cache.get(key) != null) return cache.get(key);
        if (left1 > right1) return false;
        if (left1 == right1) return bytes1[left1] == bytes2[left2];
        //切割
        for (int i = left1; i <= right1; i++) {
            //分割之后没有交换
            boolean b = dfs(bytes1, bytes2, left1, i, left2, left2 + i - left1) && dfs(bytes1, bytes2, i + 1, right1, right2 - (right1 - i - 1), right2);
            //分割之后交换了;
            if (b || (dfs(bytes1, bytes2, left1, i, right2 - (i - left1), right2) && dfs(bytes1, bytes2, i + 1, right1, left2, left2 + (right1 - i - 1)))) {
                cache.put(key, true);
                return true;
            }
            cache.put(key, false);
        }
        cache.put(key, false);
        return false;
    }

    private boolean check(byte[] bytes1, byte[] bytes2, int left1, int right1, int left2, int right2) {
        int sum = 0;
        for (int i = left1; i <= right1; i++) {
            sum += bytes1[i];
        }
        for (int i = left2; i <= right2; i++) {
            sum -= bytes2[i];
        }
        return sum == 0;
    }


    public static void main(String[] args) {
        Map<String, String> cases = new HashMap<>();
        cases.put("great", "rgeat");
        cases.put("abcde", "caebd");
        ScrambleString87 s = new ScrambleString87();
        for (String key : cases.keySet()) {
            boolean scramble = s.isScramble(key, cases.get(key));
            System.out.println(key + "\t" + cases.get(key) + "\t" + scramble);
        }

    }

}
